#pragma once

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <vector> //使用vector时需要的头文件
using namespace std;

/*****定义结构体*****/
struct btnode
{
    int data;
    struct btnode *lc, *rc;
}; //*btnode, *btree;
typedef struct btnode btnode;
typedef struct btnode *btree;
/*****定义结构体*****/

/*****利用中序遍历判断是否为BST*****/
vector<int> v;
void inOrder(btree rt)
{
    if (rt == nullptr)
    {
        return;
    }

    inOrder(rt->lc);
    v.push_back(rt->data);
    inOrder(rt->rc);
}

bool isBST(btree rt)
{
    inOrder(rt);
    for (int i = 1; i < v.size(); i++)
    {
        if (v[i - 1] >= v[i])
        {
            return false;
        }
    }

    return true;
}

bool IsBST(btree rt)
{
    bool b = isBST(rt);
    v.clear(); //在头文件中，v是一个全局变量，为了方便使用，这里每次调用后都清空v
    return b;
}
/*****利用中序遍历判断是否为BST*****/

/*****找到父节点*****/
btree findF(int k, btree root)
{
    if (root != nullptr && k == root->data || root == nullptr)
    {
        return nullptr;
    }
    else
    {
        if (root->lc != nullptr && k == root->lc->data || root->rc != nullptr && k == root->rc->data)
        {
            return root;
        }
        btree ln = findF(k, root->lc);
        btree rn = findF(k, root->rc);
        if (ln != nullptr)
        {
            return ln;
        }
        if (rn != nullptr)
        {
            return rn;
        }
    }
    return nullptr;
}
/*****找到父节点*****/

/*****声明二叉树结点*****/
btree t0, t1, t2, t3, t4, t5, t6, t7, t8, t9;
/*****声明二叉树结点*****/

/*****初始化二叉树*****/
void t_init()
{
    t1->data = 1;
    t2->data = 2;
    t3->data = 3;
    t4->data = 4;
    t5->data = 5;
    t6->data = 6;
    t7->data = 7;
    t8->data = 8;
    t9->data = 9;
    t1->lc = nullptr;
    t1->rc = nullptr;
    t2->lc = nullptr;
    t2->rc = nullptr;
    t3->lc = nullptr;
    t3->rc = nullptr;
    t4->lc = nullptr;
    t4->rc = nullptr;
    t5->lc = nullptr;
    t5->rc = nullptr;
    t6->lc = nullptr;
    t6->rc = nullptr;
    t7->lc = nullptr;
    t7->rc = nullptr;
    t8->lc = nullptr;
    t8->rc = nullptr;
    t9->lc = nullptr;
    t9->rc = nullptr;
}
/*****初始化二叉树*****/

/***打印二叉树***/
void print_t(btree t)
{
    if (t != NULL)
    {
        printf("当前结点为%d   ", t->data);
        if (t->lc != NULL)
        {
            printf("左结点为%d    ", t->lc->data);
        }
        else
        {
            printf("左结点为空   ");
        }
        if (t->rc != nullptr)
        {
            printf("右结点为%d\n", t->rc->data);
        }
        else
        {
            printf("右结点为空\n");
        }
        if (t->lc != nullptr)
        {
            print_t(t->lc);
        }
        if (t->rc != nullptr)
        {
            print_t(t->rc);
        }
    }
    else
    {
        printf("二叉树为空！\n");
    }
}
/***打印二叉树***/